package Exercise;

/**
 * Description：
 * Author: zhangc
 * Date：2017/8/3 15:32
 */
public class BinarySearch {

    public int getPos(int[] A, int n, int val) {
        if (A == null || A.length <= 0)
            return -1;
        return getPos(A, 0, A.length, val);
    }

    private int getPos(int[] A, int low, int high, int val) {
        if (low < high)
            return -1;
        int mid = (low + high) >> 1;
        if (A[ mid ] == val && (mid == low || A[ mid - 1 ] != val))
            return mid;
        else if (A[ mid ] <= val)
            return getPos(A, low, mid - 1, val);
        else
            return getPos(A, mid + 1, high, val);

    }

    public int getPosNo(int[] A, int n, int val) {
        if (A == null || A.length <= 0)
            return -1;
        int mid, low = 0, high = A.length - 1;
        while (low <= high) {
            mid = (low + high) >> 1;
            if (A[ mid ] == val && (mid == low || A[ mid - 1 ] != val))
                return mid;
            else if (A[ mid ] >= val)
                high = mid - 1;
            else low = mid + 1;
        }
        return -1;
    }

}
